package LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/combination-sum-ii/description/
 * Given a set of candidate numbers (C) (without duplicates)
 * and a target number (T),
 * find all unique combinations in C where the candidate numbers sums to T.
 * The same repeated number may be chosen from C unlimited number of times.
 * Note:
 * All numbers (including target) will be positive integers.
 * The solution set must not contain duplicate combinations.
 * For example, given candidate set [2, 3, 6, 7] and target 7,
 * A solution set is:
 * [
 * [7],
 * [2, 2, 3]
 * ]
 */
public class LC_040_CombinationSumII_DFS_BackTracking {
    public static void main(String[] args) {
        int[] candidates = {1, 2, 3, 4, 5};
        int target = 6;
        List<List<Integer>> res = Solution.combinationSum(candidates, target);
        System.out.println(res.toString());
    }

    static class Solution {
        static List<List<Integer>> combinationSum(int[] num, int target) {
            List<List<Integer>> res = new ArrayList<>();
            if (num == null || num.length == 0)
                return res;
            Arrays.sort(num);
            helper(num, 0, target, new ArrayList<>(), res);
            return res;
        }

        private static void helper(int[] num, int start, int target, ArrayList<Integer> item, List<List<Integer>> res) {
            if (target == 0) {
                res.add(new ArrayList<>(item));
                return;
            }
            if (target < 0 || start >= num.length)
                return;
            for (int i = start; i < num.length; i++) {
                if (i > start && num[i] == num[i - 1])
                    continue;
                item.add(num[i]);
                helper(num, i + 1, target - num[i], item, res);
                item.remove(item.size() - 1);
            }
        }
    }
}
